package com.lc.lc54;

import java.util.*;


public class Test {

}

class Solution {
    public List<Integer> spiralOrder(int[][] matrix) {
        int m = matrix.length;
        int n = matrix[0].length;
        int cnt = m * n;
        int[][] dir = {{0, 1},{1, 0},{0, -1},{-1, 0}};
        int t = 0;
        List<Integer> res = new ArrayList<>();
        int x = 0, y = 0;
        boolean[][] vis = new boolean[m][n];
        for (int i = 1; i <= cnt; i ++) {

        	res.add(matrix[x][y]);
        	vis[x][y] = true;
        	int nextX = x + dir[t % 4][0];
        	int nextY = y + dir[t % 4][1];
        	if (nextX >= m || nextX < 0 || nextY >= n || nextY < 0 || vis[nextX][nextY]) {
        		t ++;
        	}
        	x += dir[t % 4][0];
        	y += dir[t % 4][1];
        }
        return res;
    }
}
